#pragma once

#include <algorithm>
#include <vector>

namespace solution_090
{

class Solution
{
public:
    std::vector< std::vector<int> > subsetsWithDup(std::vector<int>& nums)
    {
        std::sort(nums.begin(), nums.end());
        m_nums = &nums;
        std::vector<int> path;
        for (int k = 0; k <= (int)nums.size(); ++k) {
            path.clear();
            backtrack(path, 0, k);
        }
        return m_subsets;
    }

private:
    void backtrack(std::vector<int>& path, int first, int k)
    {
        int curr_len = path.size();
        if (curr_len == k) {
            m_subsets.push_back(path);
            return;
        }

        for (int i = first; i < (int)m_nums->size(); ++i) {
            if (i > first && m_nums->at(i) == m_nums->at(i - 1))
                continue;
            path.push_back(m_nums->at(i));
            backtrack(path, i + 1, k);
            path.pop_back();
        }
    }

    const std::vector<int>* m_nums;
    std::vector< std::vector<int> > m_subsets;
};

}  /* namespace solution_090 */
